/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//用栈实现队列
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <Stdbool.h>
void Swap(int* a , int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
} 
void AdjustDown(int* a,int size,int root)
{
    int parent = root;
    int child = parent*2+1;
    while(child<size)
    {
        if(child+1<size&&a[child]<a[child+1])
            child++;
        if(a[parent]<a[child])
        {
            Swap(&a[child],&a[parent]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}

int* smallestK(int* arr, int arrSize, int k, int* returnSize) {
    * returnSize = k;
    if(arrSize==0||k==0)
        return NULL;
    int* retarr = (int*)malloc(sizeof(int)*k);
    for(int i=0;i<k;i++)
    {
        retarr[i]=arr[i];
    }
    //建堆(大堆)
    for(int i=(k-2)/2;i>=0;i--)
    {
        AdjustDown(retarr,k,i);
    }

    for(int i = k;i<arrSize;i++)
    {
        if(arr[i]<retarr[0])
            Swap(&arr[i],&retarr[0]);
        AdjustDown(retarr,k,0);
    }
    return retarr;
}